package Graph;

import java.util.Vector;

public class SparseGraph implements Graph{

    private int n;  //节点数
    private int m;  //边
    private boolean directed;
    private Vector<Integer>[] vector;

    public SparseGraph(int n, boolean directed) {
        if (n <= 0) {
            throw new IllegalArgumentException("n is illegal");
        }
        this.n = n;
        this.m = 0;
        this.directed = directed;
        vector = new Vector[n];
        for (int i = 0; i < n; i++) {
            vector[i] = new Vector<Integer>();
        }
    }

    public int V() {
        return n;
    } // 返回节点个数

    public int E() {
        return m;
    } // 返回边的个数


    //向图中添加一个边
    public void addEdge(int v, int w) {
        assert v > 0 && v < n;
        assert w > 0 && w < n;

        vector[v].add(w);
        if (v != w && !directed) {
            vector[w].add(v);
        }

        m++;

    }

    public boolean hasEdge(int v, int w) {
        assert v > 0 && v < n;
        assert w > 0 && w < n;

        for (int i = 0; i < vector[v].size(); i++) {
            if (vector[v].elementAt(i) == w) {
                return true;
            }
        }

        return false;
    }

    // 返回图中一个顶点的所有邻边
    public Iterable<Integer> adj(int v) {
        assert v > 0 && v < n;
        return vector[v];
    }

    // 显示图的信息
    public void show(){

        for( int i = 0 ; i < n ; i ++ ){
            System.out.print("vertex " + i + ":\t");
            for( int j = 0 ; j < vector[i].size() ; j ++ )
                System.out.print(vector[i].elementAt(j) + "\t");
            System.out.println();
        }
    }


}
